package 题目集.倍增算法.st表;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;

/**
 * st表解决的是一个可重复贡献问题,即(l,r)问题的解，是(l,逼近r)，(逼近l,r)的解有关。且可以允许这两个区间重合一部分.例如区间最大值，或者公约数
 * st表的优势，st表在构建时，时间复杂度为O(nlogn)，查询时，时间复杂度为O(1)
 * https://www.acwing.com/problem/content/description/1276/
 * 给定一个长度为
 * N 的数列，和
 * M 次询问，求出每一次询问的区间内数字的最大值与最小值的差。
 */
public class ch01_静态区间最大值 {
    /**
     * st表解法：记录下每个位置开始，长度为1的最大值，长度为2的最大值，长度为4的最大值...
     * 当询问l,r范围内最大值时，其实就是求l为起始位置，长度为2^k次方。（2^k次方逼近于r-l），与r为终点位置，长度为2^k次方的最大值。
     */
    static int maxN = (int) (1e5 + 10), maxM = (int) (2e6 + 10);
    static int maxPow = (int) Math.ceil(Math.log(maxN) / Math.log(2));
    static int[][] stMax = new int[maxN][maxPow];
    static int[][] stMin = new int[maxN][maxPow];
    static int n, m, power;

    public static void main(String[] args) {
        Reader sc = new Reader();
        n = sc.nextInt();
        m = sc.nextInt();
        power = (int) Math.ceil(Math.log(n) / Math.log(2));
        for (int[] ints : stMin) {
            Arrays.fill(ints,Integer.MAX_VALUE);
        }
        for (int i = 0; i < n; i++) {
            stMax[i][0] = sc.nextInt();
            stMin[i][0] = stMax[i][0];
        }
        build();
        int l, r, len, k, max,min;
        for (int i = 0; i < m; i++) {
            l = sc.nextInt() - 1;
            r = sc.nextInt() - 1;
            if (l == r) {
                System.out.println(0);
                continue;
            }
            len = r - l + 1;    //左闭右闭，额外+1
            k = (int) Math.ceil(Math.log(len) / Math.log(2)) - 1;    //逼近于len的2^k次方，因为是逼近，所以不能等于，先向上取整再-1
            //以l为起点，长度为2^k的最大值，与 r位置为终点，长度为2^k的最大值
            //r - (1 << k) + 1，额外+1是因为r是终点，而r-(1<<k)不包含r
            max = Math.max(stMax[l][k], stMax[r - (1 << k) + 1][k]);
            min = Math.min(stMin[l][k], stMin[r - (1 << k) + 1][k]);
            System.out.println(max-min);
        }
    }

    public static void build() {
        for (int p = 1; p < power; p++) {
            int pn = 1 << (p - 1);
            for (int i = 0; i < n; i++) {
                /**
                 * i位置长度为2^p次方的最大值为：
                 *  max（i位置长度为2^(p-1)最大值，i右移2^(p-1)位置长度为2^(p-1)的最大值）
                 */
                stMax[i][p] = Math.max(stMax[i][p - 1], stMax[i + pn][p - 1]);
                stMin[i][p] = Math.min(stMin[i][p - 1], stMin[i + pn][p - 1]);
            }
        }
    }


    static class Reader {
        static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

        public Reader(Object... o) {
        }

        public int nextInt() {
            try {
                in.nextToken();
            } catch (Exception ignored) {
            }
            return (int) in.nval;
        }
    }
}
